問題一覧 > 通常問題

No.599 回文かい

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 256 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 112
作問者 : koyumeishikoyumeishi / テスター : confconf
4 ProblemId : 1171 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2017-11-18 00:51:33

問題文

"水道水" は回文
それ 回文かい!

文字列 Sk(1) 個の空でない部分文字列に分解し、 先頭から順に T1,T2,,Tk とします。
(S=T1+T2++Tk , |Ti|1)
全ての i(1ik) について Ti=Tki+1 が成り立つとき、 列T(=[T1,T2,,Tk]) は文字列 S回文かい分解 であるといいます。

文字列 S が与えられるので、 何通りの 回文かい分解 が考えられるか計算してください。
答えが非常に大きくなる場合があるので、 1,000,000,007 で割った余りを出力してください。

入力

S

S は次の制約を満たします。
1|S|104
S は 小文字のアルファベット 'a' - 'z' のみで構成される

出力

何通りの 回文かい分解 が考えられるか、1,000,000,007 で割った余りを出力してください。

サンプル

サンプル1
入力
abc
出力
1

T = ["abc"] が 回文かい分解 になります。

サンプル2
入力
suidousui
出力
2

T = ["suidousui"]
T = ["sui", "dou", "sui"]

サンプル3
入力
kaibunkaibunkai
出力
3

T = ["kaibunkaibunkai"]
T = ["kai", "bunkaibun", "kai"]
T = ["kai", "bun", "kai", "bun", "kai"]

サンプル4
入力
aaaaa
出力
4

T = ["aaaaa"]
T = ["aa", "a", "aa"]
T = ["a", "aaa", "a"]
T = ["a", "a", "a", "a", "a"]

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。